/**
 * Creared with IntelliJ IDEA.
 * Description:哈希函数
 * User:yxd
 * Date:2022-02-28
 * Time:20:38
 */
public class MyHashBuck {
     private static final double DEFAULT_LOADFACTOR = 0.75;//默认的负载因子
     static class Node{
        public int key;
        public int val;
        public Node next;
        public Node(int key,int val){
            this.key = key;
            this.val = val;
        }
    }
    public Node[] array;//初始存放地址的数组，数组内存放的是链表头的地址
    public int usedSize;
    public MyHashBuck(){//初始化数组
        this.array = new Node[10];
    }

    /**
     * put方法
     * @param key
     * @param val
     */
    public void put(int key,int val){
        int index = key % array.length;//1.找到key所在的位置
        Node cur = array[index];//2.遍历这个下标的元素看有没有这个key
        while(cur != null){
            if(cur.key == key){
                cur.val = val;//更新
                break;
            }
            cur = cur.next;
        }
        //3.没这个key的元素，需要尾插或者头插
        cur = array[index];
        Node node = new Node(key,val);
        if(cur == null){
            array[index] = node;
        }else{
            while(cur.next != null){
                cur = cur.next;
            }
            cur.next = node;
        }
        this.usedSize++;
        //4.检查负载因子是否超出，如果超出需要扩容
        if(loadFactor() > DEFAULT_LOADFACTOR){
            resize();
        }
    }
    //隐藏类的实现细节，需要给特定的方法封装一下
    private void resize(){
        //扩容不仅仅是扩大数组长度，应该把所有的元素重新哈希一遍，保证合理利用空间，且所有元素都应在其扩容后应在的位置
        Node[] newArray = new Node[array.length * 2];
        for(int i = 0;i < array.length;i ++){
            Node cur = array[i];
            while(cur != null){
                int index = cur.key % newArray.length;
                Node curNext = cur.next;//保存这个节点之后的节点，方便后面的节点再放到新数组中
                //以头插或者尾插的方式再放到新链表里面
                //尾插
                if(newArray[index] == null){
                    newArray[index] = cur;
                    newArray[index].next = null;
                }else{
                    Node z = newArray[index];
                    while(z.next != null){
                        z = z.next;
                    }
                    z.next = cur;
                    z = z.next;
                    z.next = null;
                }
                cur = curNext;
                //头插
                /*cur.next = newArray[index];//先绑定后面
                newArray[index] = cur;//在绑定前面
                cur = curNext;*/
            }
        }
        array = newArray;
    }
    private double loadFactor(){//获得此时的负载因子
        return 1.0 * usedSize / array.length;
    }
    /**
     * get方法
     * @param key
     * @return
     */
    public int get(int key){
        int index = key % array.length;//1.找到key所在的位置
        Node cur = array[index];//2.遍历这个下标的元素看有没有这个key
        while(cur != null){
            if(cur.key == key){
                return cur.val;
            }
            cur = cur.next;
        }
        return -1;//没找到
    }

    public static void main(String[] args) {
        MyHashBuck myHashBuck = new MyHashBuck();
        myHashBuck.put(1,1);
        myHashBuck.put(12,34);
        myHashBuck.put(2,15);
        myHashBuck.put(4,5);
        myHashBuck.put(5,6);
        myHashBuck.put(8,9);
        myHashBuck.put(213,31);
        myHashBuck.put(321,432);
        /*myHashBuck.put(1,6);
        myHashBuck.put(4,43);
        myHashBuck.put(5,3);8*/

        System.out.println(myHashBuck.get(5));

    }
}
